/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
 var maxValue = function(root, k) {
    function DPNode(val){
        this.val=val;
        this.link=new Array(k+1).fill(val);
        this.link[0]=0;
        this.left=this.right=null;
    }
    let dp=new DPNode(root.val,1);
    function replicate(r,dr){
        if(r.left){
            dr.left=new DPNode(r.left.val,1);
            replicate(r.left,dr.left);
        }
        if(r.right){
            dr.right=new DPNode(r.right.val,1);
            replicate(r.right,dr.right);
        }
    }
    replicate(root,dp);
    function traverseDP(node){
        if(node.left){
            traverseDP(node.left);
        }
        if(node.right){
            traverseDP(node.right);
        }
        if(node.right&&node.left){
            //node.link[2]+=Math.max(node.left.link[1]+node.right.link[0],node.right.link[1]+node.left.link[0]);
            node.link[1]+=node.left.link[0]+node.right.link[0];
            node.link[0]=Math.max(...node.left.link)+Math.max(...node.right.link);
            for(let i=2;i<=k;i++){
                let t=0;
                for(let j=0;j<i;j++){
                    t=Math.max(node.left.link[j]+node.right.link[i-1-j],t);
                }
                node.link[i]+=t;
            }
        }
        else if(node.left){
            node.link[0]=Math.max(...node.left.link);
            for(let i=0;i<k;i++){
                node.link[i+1]+=node.left.link[i];
            }
        }
        else if(node.right){
            node.link[0]=Math.max(...node.right.link);
            for(let i=0;i<k;i++){
                node.link[i+1]+=node.right.link[i];
            }
        }
        //console.log(node.val,node.link);
        //ret=Math.max(ret,...node.link);
    }
    traverseDP(dp);
    return Math.max(...dp.link);
};